//统计一个数字在排序数组中出现的次数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2 
//
// 示例 2: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: 0 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// 
//
// 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-
//position-of-element-in-sorted-array/ 
// Related Topics 数组 二分查找 👍 314 👎 0

package leetcode.editor.offer;

// 53. 数字在排序数组中出现的次数
// https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/submissions/
class ZaiPaiXuShuZuZhongChaZhaoShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new ZaiPaiXuShuZuZhongChaZhaoShuZiLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 二分法
         *
         * @param nums
         * @param target
         * @return
         */
        /*public int search(int[] nums, int target) {
            if (nums.length == 0) {
                return 0;
            }
            int left = 0;
            int right = nums.length - 1;
            // 搜索有边界
            while (left <= right) {
                int mid = (left + right) / 2;
                if (target >= nums[mid]) {
                    left = mid + 1;
                } else right = mid - 1;
            }

            int edgeRight = left;  // 获取到右边界

            // 若数组中无 target ，则提前返回
            if (right > 0 && nums[right] != target) return 0;

            left = 0;
            right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (target > nums[mid]) {
                    left = mid + 1;
                } else right = mid - 1;
            }

            int edgeLeft = right;

            return edgeRight - edgeLeft - 1;
        }*/

        /**
         * 哈希表
         *
         * @param nums
         * @param target
         * @return
         */
//        public int search(int[] nums, int target) {
//            HashMap<Integer, Integer> map = new HashMap<>();
//            for (int i = 0; i < nums.length; i++) {
//                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//            }
//            return map.get(target) == null ? 0 : Integer.valueOf(map.get(target));
//        }

        // 两次二分
        public int search(int[] nums, int target) {
            int left = getLeft(nums, target);
            int right = getRight(nums, target);
            return right - left;
        }

        private int getRight(int[] nums, int target) {
            int l = 0, r = nums.length;
            while (l < r) {
                int m = (l + r) / 2;
                if (nums[m] < target) {
                    l = m + 1;
                }else r = m;
            }

            return r;
        }

        private int getLeft(int[] nums, int target) {
            int l = 0, r = nums.length;
            while (l < r) {
                int m = (l + r) / 2;
                if (nums[m] > target) {
                    r = m;
                }else l = m + 1;
            }

            return l;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
